package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * @author lixiaowen
 * @create 2019-12-14
 */
public class MergekSortedLists23 {


    /**
     * 分治法
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        //记录数组的逻辑长度
        int len = lists.length;
        while (len > 1) {
            //有点像希尔排序吧?
            int mid = (len + 1) / 2;
            //i < len/2 防止len=偶数时出现越界
            for (int i = 0; i < len / 2; i++) {
                lists[i] = mergeTwoList(lists[i], lists[i + mid]);
            }
            len = mid;
        }
        return lists[0];
    }


    /**
     * 合并两个有序链表
     *
     * @param node1
     * @param node2
     * @return
     */
    private ListNode mergeTwoList(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(-1), pre = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                pre.next = node1;
                pre = node1;
                node1 = node1.next;
            } else {
                pre.next = node2;
                pre = node2;
                node2 = node2.next;
            }
        }
        //拼接剩下的元素
        if (node1 == null) {
            pre.next = node2;
        } else {
            pre.next = node1;
        }
        return dummy.next;
    }


    public static void main(String[] args) {
        int r = 3;
        int c = 6;
        int[][] arrs = new int[r][c];
        ListNode[] lists = new ListNode[r];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                arrs[i][j] = new Random().nextInt(r * c);
            }
            Arrays.sort(arrs[i]);
            lists[i] = ListNode.build(arrs[i]);
            System.out.println(Arrays.stream(arrs[i]).boxed().collect(Collectors.toList()));
            System.out.println(lists[i]);
        }
        MergekSortedLists23 merge = new MergekSortedLists23();
        ListNode node = merge.mergeKLists(lists);
        System.out.println(node);
    }
}
